// 老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。

// 你需要按照以下要求，帮助老师给这些孩子分发糖果：

// 每个孩子至少分配到 1 个糖果。
// 相邻的孩子中，评分高的孩子必须获得更多的糖果。
// 那么这样下来，老师至少需要准备多少颗糖果呢？

// 示例 1:

// 输入: [1,0,2]
// 输出: 5
// 解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。
// 示例 2:

// 输入: [1,2,2]
// 输出: 4
// 解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。
//      第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

#include <vector>
#include <set>
#include <numeric>
#include <iostream>
#include <algorithm>

using std::max;
using std::cout;
using std::endl;
using std::vector;
using std::set;
using std::accumulate;

/*
[0,1,2,2,3,2,2,1]
1,2,3,1,2,1,2,1,
首先初始化每个人一个糖果，然后这个算法需要遍历两遍，
第一遍从左向右遍历，如果右边的小盆友的等级高，等加一个糖果，
这样保证了一个方向上高等级的糖果多。
然后再从右向左遍历一遍，如果相邻两个左边的等级高，
而左边的糖果又少的话，则左边糖果数为右边糖果数加一。
*/
class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        vector<int> nums(n, 1);
        for (int i = 0; i < n - 1; ++i) { // 从左向右遍历
            if (ratings[i+1] > ratings[i]) nums[i+1] = nums[i] + 1;
        }
        for (int i = n-1; i > 0; --i) { // 从右向左遍历
            // if (ratings[i-1] > ratings[i]) nums[i-1] = nums[i-1] > nums[i]+1 ? nums[i-1] : nums[i]+1;
            if (ratings[i-1] > ratings[i]) nums[i-1] = max(nums[i-1], nums[i]+1);
        }
        return accumulate(nums.begin(), nums.end(), 0);
    }
};


// 自己瞎搞的，层层向上遍历，太麻烦
class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        vector<int> res(n, 1);
        set<int> s(ratings.begin(), ratings.end()); // set默认从小到大排序
        for (auto iter = s.begin(); iter != s.end(); ++iter) { // 从小到大一层一层遍历
            int num = *iter;
            for (int i = 0; i < n; ++i) {
                if (ratings[i] == num) {
                    if (i == 0) { // 最左边
                        if (ratings[i+1] < ratings[i]) res[i] = res[i+1] + 1;
                    } else if (i == n-1) { // 最右边
                        if (ratings[i-1] < ratings[i]) res[i] = res[i-1] + 1;
                    } else {
                        if (ratings[i+1] < ratings[i] || 
                            ratings[i-1] < ratings[i])
                            res[i] = 1 + (res[i-1] < res[i+1] ? res[i-1] : res[i+1]);
                    }
                }
            }
        }
        for (auto i : res) 
            cout << i << ' ';
        cout << endl;
        return accumulate(res.begin(), res.end(), 0);
    }
};

int main() {
    Solution s;
    vector<int> ratings{29,51,87,87,72,12};
    int res = s.candy(ratings);
    cout << "res is : " << res << endl;
    return 0;
}